﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;


namespace SortCompare
{
    public static class MergeSort
    {
        public static int[] Sort(int[] input)
        {
            if (input.Length == 1)
                /* Trivial case; return input */
                return input;
            else
            {
                //split array in half
                double split = (double)input.Length / 2.0;
                int[] left = new int[(int)Math.Ceiling(split)];
                int[] right = new int[(int)Math.Floor(split)];

                //fill in the arrays
                int i = 0;
                while (i < left.Length)
                    left[i] = input[i++];
                while (i < input.Length)
                    right[i-left.Length] = input[i++];
                
                //sort each side
                left = Sort(left);
                right = Sort(right);
                return Combine(left, right);

            }

        }

        private static int[] Combine(int[] left, int[] right)
        /* Combines two sorted integer arrays into one sorted integer array */
        {
            int[] output = new int[left.Length + right.Length];

            /* combine */

            //indexes to keep track of the left and right arrays
            int rightIndex = 0, leftIndex = 0;

            for (int i = 0; i < output.Length; i++)
            {
                //Case: left array is empty
                if (leftIndex == left.Length)
                    //fill the rest of output with the remainder of right array
                    while (rightIndex < right.Length)
                        output[i++] = right[rightIndex++];

                //Case: right array is empty
                else if (rightIndex == right.Length)
                    //fill rest of output with the remainder of left array
                    while (leftIndex < left.Length)
                        output[i++] = left[leftIndex++];


                //Case: left < right
                else if (left[leftIndex] < right[rightIndex])
                    //use left array's element
                    output[i] = left[leftIndex++];
                    //increment left index

                //Case: right <= left
                else if (right[rightIndex] <= left[leftIndex])
                    //use right array's element
                    output[i] = right[rightIndex++];
                    //increment right index
            }

            return output;
        }

    }
}
